#!/usr/bin/env python 
# -*- coding:utf-8 -*-

from numpy import *
import random
from collections import deque
from math import *

def VtrAds(page):
    isaddress = [0 for m in range(320)]  #存放虚拟地址的数组
    print(isaddress)
    #p = random.randint(0, 318)
    #isaddress[0] = p
    for i in range(320):
        isaddress[i] = i
        #p = isaddress[i]
        #r = random.random()
        #if r < 0.5:
            #isaddress[i+1] = p
        #elif r < 0.75:
            #isaddress[i+1] = random.randint(0, p)
        #else: isaddress[i+1] = random.randint(p, 320)
    print("isadress:",isaddress)
    for n in range(320):
        page[n] = math.floor(isaddress[n]/10)
    print(page)
    return page

def FIFO(frame, page):
    lzh = deque([])  # 列表lzh最多(在填满后不多不少)frame个元素，用来实现LRU算法
    count = 0  # count用于计算缺页次数
    flag = True  # True表示缺页
    for i in range(320):  # i从第一个元素开始
        if page[i] not in lzh:  # 如果i不在lzh中，即缺页
            flag = True  # 表示缺页
            if len(lzh) < frame:  # 如果lzh的长度还没到达3
                lzh.append(page[i])  # 就在其尾部添加i
            else:  # 如果lzh的长度已经到达frame了
                lzh.pop()
                lzh.append(page[i])
            count += 1  # 缺页的，记录之
        else:  # 如果i在lzh中，即不缺页
            flag = False  # 表示不缺页
            #lzh[lzh.index(page[i]):len(lzh) - 1:] = lzh[lzh.index(page[i]) + 1::]  # 将i之后的元素都复制到i开始向后的位置，并在最后留一个空位保证不改变lzh长度
            #lzh[len(lzh) - 1::] = [page[i]]  # 将最后一个元素用i覆盖
    #print("FIFO算法结束，总的缺页次数为", count)
    print("命中率", 1 - (float(count)/len(page)))
    print("\n")
    return 1 - (float(count) / len(page))



def OPT(frame, page):
    cache = []
    count = 0
    # 对于需要的每个页面
    for i in range(len(page)):
        # 如果已经在cache里面
        if page[i] in cache:
            continue  # 直接使用就行了,进入下一次
        # 如果不在,但cache未满
        elif len(cache) < frame:
            cache.append(page[i])  # 把页面加入进来
        else:  # OPT的核心(如果cache满时缺页)
            count +=1
            cache = lossOpt(cache, page, i)  # 更新cache
    print("命中率:",1-(float(count) / len(page)))
    print("\n")
    return 1-(float(count) / len(page))

#用于在Opt算法下更新cache
def lossOpt(cache,page,i):
#bye数组记录哪个页不要了
    bye=[False for j in range(len(cache))]
    num=0 #记录已经有几个要留下
    #循环去看后面的每个页pageno[j]
    for j in range(i+1, len(page)):
        if num==len(cache)-1: #如果已经找到这么多
            break
        #如果有新的缺页项
        if (page[j] in cache) \
                and (bye[cache.index(page[j])]==False):
                    num+=1 #新的缺页项
                    bye[cache.index(page[j])]=True
    #拿掉那个还是False的
    #即使后面的元素不够多,在循环体外拿掉也是正确的
    for k in range(len(bye)):
        if bye[k]==False:
            del cache[k]
            break #拿掉一个就退出!
    return cache #返回新的cache

def LRU(frame, page):
    count = 0
    lzh = deque([])
    for i in range(len(page)):  # i从第一个元素开始
        if page[i] not in lzh:  # 如果i不在lzh中，即缺页
            flag = True  # 表示缺页
            if len(lzh) < frame:  # 如果lzh的长度还没到达3
                lzh.append(page[i])  # 就在其尾部添加i
            else:  # 如果lzh的长度已经到达frame了
                m = lzh.pop()
                lzh.pop()
                lzh.append(m)
            count += 1  # 缺页的，记录之
        else:  # 如果i在lzh中，即不缺页
            flag = False  # 表示不缺页
            #lzh[lzh.index(page[i]):len(lzh) - 1:] = lzh[lzh.index(page[i]) + 1::]  # 将i之后的元素都复制到i开始向后的位置，并在最后留一个空位保证不改变lzh长度
            #lzh[len(lzh) - 1::] = [page[i]]  # 将最后一个元素用i覆盖
    print("命中率", (1 - float(count)/320))
    print("\n")
    return (1 - float(count)/320)



#入口函数
def main():
    #page = [-1 for i in range(320)]
    print ("test")
    page = deque([0 for i in range(320)])
    VtrAds(page)  # 生成地址表page
    for i in range(4, 33):
        FIFO(i, page)
        LRU(i,  page)
        OPT(i, page)
        print("\n")


if __name__ == "__main__":
    main()



